package com.mid;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created by Lxk on 2020/1/24.
 */
public class Solution113 {

    private List<List<Integer>> res = new ArrayList<>();

    private void findPath(TreeNode cur, Stack<TreeNode> path, int remainTarget) {
        if (cur.left == null && cur.right == null) {
            path.push(cur);
            if (Integer.valueOf(cur.val).equals(remainTarget)) {
                //find
                List<Integer> curRes = new ArrayList<>();
                for (TreeNode node : path) {
                    curRes.add(node.val);
                }
                res.add(curRes);
                path.pop();
                return;
            } else {
                //not find
                path.pop();
                return;
            }
        }
        path.push(cur);
        if (cur.left != null) {
            findPath(cur.left, path, remainTarget - cur.val);
        }
        if (cur.right != null) {
            findPath(cur.right, path, remainTarget - cur.val);
        }
        path.pop();
    }

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        findPath(root, stack, sum);
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode node4 = new TreeNode(4);
        TreeNode node8 = new TreeNode(8);
        TreeNode node11 = new TreeNode(11);
        TreeNode node13 = new TreeNode(13);
        TreeNode node4d = new TreeNode(4);
        TreeNode node7 = new TreeNode(7);
        TreeNode node2 = new TreeNode(2);
        TreeNode node5 = new TreeNode(5);
        TreeNode node1 = new TreeNode(1);
        root.left = node4;
        root.right = node8;
        node4.left = node11;
        node8.left = node13;
        node8.right = node4d;
        node11.left = node7;
        node11.right = node2;
        node4d.left = node5;
        node4d.right = node1;
        Solution113 solution113 = new Solution113();
        System.out.println(solution113.pathSum(root, 22));
    }

}
